import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Home-pc
 * Date: 2023-08-25
 * Time: 9:39
 */
public class TestHeap {
    //利用数组存储
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    @Override
    public String toString() {
        return "TestHeap{" +
                "elem=" + Arrays.toString(elem) +
                ", usedSize=" + usedSize +
                '}';
    }

    //创建一个大根堆
    public void createHeap(int[] array){
        for (int i = 0; i <array.length; i++) {
            elem[i]=array[i];
            usedSize++;//每添加一个元素，usedSize加1
        }
        //向下调整
        for (int parent = (usedSize-1-1)/2; parent >=0; parent--) {
            shiftDown(parent,usedSize);//这里是针对的一个节点下的树
        }
    }
    private void shiftDown(int parent,int len){
        int child=2*parent+1;//左孩子
        while(child<len){//这里child不会越界，下面保证child+1不会越界
            if(child+1<len && elem[child]<elem[child+1]){//找到孩子节点中值较大的那个
                child=child+1;
            }
            if(elem[child]>elem[parent]){//和父亲节点比较，如果大于父亲节点，则交换数值
                int temp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=temp;
                parent=child;//先将child赋值给parent，partent向下移
                child=parent*2+1;
            }else{
                break;//在该节点的树下，已是大根堆
            }
        }
    }

    //插入数据
    public void push(int val){
        if(isFull()){
            elem=Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize]=val;
        usedSize++;
        shiftUp(usedSize-1);
    }
    public boolean isFull(){
        return usedSize==elem.length;
    }
    public void shiftUp(int child){
        int parent=(child-1)/2;
        while(child>0){
            if(elem[child]>elem[parent]){
                int temp=elem[child];
                elem[child]=elem[parent];
                elem[parent]=temp;
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }

    }

    //删除堆顶的元素
    public void  poll() {
        if(empty()){
            throw new HeapEmptyException("删除，堆为空");
        }
        int temp=elem[0];
        elem[0]=elem[usedSize-1];
        elem[usedSize-1]=temp;
        usedSize--;
        shiftDown(0,usedSize);
    }
    public boolean empty(){
        return usedSize==0;
    }


        public void heapSort(){
            int end=usedSize-1;
            while(end>0){
                int temp=elem[0];
                elem[0]=elem[end];
                elem[end]=temp;
                shiftDown(0,end);
                end--;
            }
        }

}


